1. Field of the Invention
The present invention relates to a multiple-pairs shortest path problem. More particularly, the present invention relates to a method and system for solving the multiple-pairs shortest path problem faster.
2. Description of the Related Art
Conventionally, as a solution to the problem of shortest paths from multiple sources to multiple destinations (multiple-pairs shortest path problem), a technique has been known, in which the shortest path problem from a single source to multiple destinations is applied to multiple sources. For example, Japanese Patent Application Publication No. 2001-125882 describes that each node corresponding to an intersection on a map and a link cost (distance) associated therewith are separated to be independent of each other to find a path using the Dijkstra method while managing them in an adjacency matrix or an adjacency list, respectively. Japanese Patent Application Publication No. 2001-125882 proposes an efficient data structure for solving the shortest path problem from a single source to multiple destinations, but it is not a technique for speedup of the shortest path problem itself.
Sebastian Knopp, Peter Sanders, Dominik Schultes, Frank Schulz, Dorothea Wagner, “Computing Many-to-Many Shortest Paths Using Highway Hierarchies,” ALENEX, 2007 solves the shortest path problem (many-to-many) from multiple sources to multiple destinations. Sebastian Knopp et al. describe a method of searching for a road information network. The method includes a step of preprocessing an input graph and a step of applying a modified version of the Dijkstra method to the preprocessed graph. Sebastian Knopp et al. do not offer a method of solving the all-pairs shortest path problem faster. However, Sebastian Knapp et al. has a preprocessing section in which the Dijkstra method is applied to solve the all-pairs shortest path problem (all-to-all).